#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

/*
    bigger > 0;
    equal == 0;
    else < 0;
 */
typedef int (*cmp)(void* v1, void* v2);

struct usortvalue{
    void* v;
    int idx;
};


struct usortarray{
    struct usortvalue* set;
    int num;
    int num_total;

    cmp c;
};


uintptr_t usortarray_init(size_t num_total, cmp c)
{
    uintptr_t retp = (uintptr_t)0;

    struct usortarray* sort = malloc(sizeof(struct usortarray) + sizeof(struct usortvalue)*num_total);
    if(NULL != sort) {
        sort->set = (void*)sort + sizeof(struct usortarray);
        sort->num = 0;
        sort->num_total = num_total;
        sort->c = c;

        retp = (uintptr_t)sort;
    }
    else {
        fprintf(stderr, "malloc error.(%s)\n", __FUNCTION__);
    }

    return retp;
}


/*
    return the add index.  OK, it should be >= 0.  error, -1.
 */
int usortarray_add(uintptr_t p, void* v)
{
    int ret_idx = 0;

    struct usortarray* sort = (struct usortarray*)p;
    if(sort->num >= sort->num_total) {
        ret_idx = -1;
        return ret_idx;
    }
    int idx;
#if 0
    if(0 == sort->num) {
        idx = 0;
        sort->set[idx].v = v;
        sort->set[idx].idx = sort->num;
        sort->num ++;

        ret_idx = sort->set[idx].idx;
        return ret_idx;
    }
#endif

    int s, e;
    s = 0;
    e = sort->num - 1;
    while(1) {
        if(s>e) {
            idx = e + 1;             
            break;
        }
        idx = (s+e)/2;
        
        if(sort->c(v, sort->set[idx].v) >= 0) {
            s = idx + 1;
        }
        else {
            e = idx - 1;
        }
    }
    
    int i;
    for(i=sort->num-1; i>= idx; i--) {
        sort->set[i+1] = sort->set[i];
    }

    sort->set[idx].v = v;
    sort->set[idx].idx = sort->num;
    sort->num ++;

    ret_idx = sort->set[idx].idx;
    return ret_idx;
}


/*
    return the add index.  OK, it should be >= 0.  error, -1.
 */
int usortarray_get(uintptr_t p, void* v)
{
    int ret_idx = 0;

    struct usortarray* sort = (struct usortarray*)p;
    if(sort->num >= sort->num_total) {
        ret_idx = -1;
        return ret_idx;
    }

    int idx;
    if(0 == sort->num) {
        idx = 0;
        sort->set[idx].v = v;
        sort->set[idx].idx = sort->num;
        sort->num ++;

        ret_idx = sort->set[idx].idx;
        return ret_idx;
    }

    int s, e;
    s = 0;
    e = sort->num - 1;
    while(1) {
        if(s>e) {
            idx = e + 1;             
            break;
        }
        idx = (s+e)/2;
        
        if(0 == sort->c(v, sort->set[idx].v)) {
            ret_idx = sort->set[idx].idx;
            return ret_idx;
        }
        if(sort->c(v, sort->set[idx].v) > 0) {
            s = idx + 1;
        }
        else {
            e = idx - 1;
        }
    }
    
    int i;
    for(i=sort->num-1; i>= idx; i--) {
        sort->set[i+1] = sort->set[i];
    }

    sort->set[idx].v = v;
    sort->set[idx].idx = sort->num;
    sort->num ++;

    ret_idx = sort->set[idx].idx;
    return ret_idx;
}


int usortarray_delete(uintptr_t p, void* v)
{
    int ret = 0;
    return ret;
}


int usortarray_deinit(uintptr_t p)
{
    int ret = 0;
    struct usortarray* sort = (struct usortarray*)p;
    free(sort);
    return ret;
}


int cmp_int(void* v1, void* v2)
{
    return (int)v1 - (int)v2;
}


int main()
{
    int test_times = 1;
while(1 || test_times--) {
    uintptr_t p = usortarray_init(1024*2, cmp_int);
    int i;
    for(i=0; i<1024*2; i+=2) {
        usortarray_add(p, (void*)i);
    }

    for(i=1; i<1024*2; i++) {
        int ret_idx = usortarray_get(p, (void*)i);
        assert(ret_idx >= 0);
        printf("idx=%4d.\n", ret_idx);
    }

    struct usortarray* sort = (struct usortarray*)p;
    for(i=0; i<1024*2; i++) {
        printf("[%4d %4d].\n", (int)sort->set[i].v, (int)sort->set[i].idx);
    }
    usortarray_deinit(p);
}

    return 0;
}
